package com.cjm.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Ti21620240602 {
    List<Integer> xx = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combine3(int k, int n) {
        res.clear();
        if (n > 50) {
            return res;
        }
        method216(0, k, n, new ArrayList<>(), 0);
        return res;
    }

    private void method216(int startIndex, int k, int n,
                           ArrayList<Integer> tmp, int cur) {
        if ( cur > n) {
            return;
        }
        if (tmp.size() > k) {
            return;
        }
        for (int i = startIndex; i < res.size(); i++) {
            int currentValue = xx.get(i) + cur;
            if (currentValue > n) {
                return;
            }
            tmp.add(xx.get(i));
            if (currentValue == n) {
                if (tmp.size() == k) {
                    res.add(new ArrayList<>(tmp));
                }
                tmp.remove(tmp.size() - 1);
                return;
            }
            method216(i+1, k , n, tmp, currentValue);
            tmp.remove(tmp.size() - 1);
        }
    }
}
